/*
题目: 和有限的最长子序列
给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。

子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

https://leetcode.cn/problems/longest-subsequence-with-limited-sum
 */
public class AnswerQueries {
    public int[] answerQueries(int[] nums, int[] queries) {
        // 前缀和 + 二分查找
        Arrays.sort(nums);
        int m = nums.length;
        int n = queries.length;

        int[] prefix = new int[m];
        prefix[0] = nums[0];
        for (int i = 1; i < m; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }

        int[] src = new int[n];
        for (int i = 0; i < n; i++) {
            src[i] = search(prefix, queries[i]) + 1;
        }
        return src;
    }

    private int search(int[] prefix, int target) {
        int left = 0;
        int right = prefix.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (prefix[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left - 1;
    }
}
